public class MyBinaryTree {
    //定义内部类TreeNode
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

    //TreeNode的构造方法
        public TreeNode(char val){
            this.val=val;
        }
    }

    //人为拼接构造一颗二叉树的方法
    public TreeNode creatTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        TreeNode I=new TreeNode('I');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        F.left=I;
        return A;//返回根节点A
    }

    //查找二叉树中是否包含值为key的节点的方法
    public TreeNode find(TreeNode root,char key){
        //空节点返回空
        if(root==null){
            return null;
        }
        //找到key值节点则返回
        if(root.val==key){
            return root;
        }
        //递归左子树
        TreeNode leftVal=find(root.left,key);
        if(leftVal!=null){
            return leftVal;
        }
        //递归右子树
        TreeNode rightVal=find(root.right,key);
        if(rightVal!=null){
            return rightVal;
        }
        //程序全部运行结束说明没有招到值为key的节点
        return null;
    }

    //前序遍历方法
    public void preOrder(TreeNode root){
        //空节点返回
        if(root==null){
            return;
        }
        //打印根节点
        System.out.print(root.val+" ");
        //递归左子树
        preOrder(root.left);
        //递归右子树
        preOrder(root.right);

    }

    //中序遍历方法
    public void inOrder(TreeNode root){
        //空节点返回
        if(root==null){
            return;
        }
        //递归左子树
        inOrder(root.left);
        //打印根节点
        System.out.print(root.val+" ");
        //递归右子树
        inOrder(root.right);

    }

    //后序遍历方法
    public void postOrder(TreeNode root){
        //空节点返回
        if(root==null){
            return;
        }
        //递归左子树
        postOrder(root.left);
        //递归右子树
        postOrder(root.right);
        //打印根节点
        System.out.print(root.val+" ");

    }

    //获取树中的节点个数的方法
    public int getSize(TreeNode root){
        //空节点返回0
        if(root==null){
            return 0;
        }
        //递归左子树和右子树（+1为根节点个数）
        int size=1+getSize(root.left)+getSize(root.right);
        return size;
    }

    //获取二叉树中叶子节点个数的方法
    public int getLeafNodeCount(TreeNode root){
        //空节点返回0
        if(root==null){
            return 0;
        }
        //叶子节点返回1
        if(root.left==null&&root.right==null){
            return 1;
        }
        //递归左子树和右子树
        int count=getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
        return count;
    }

    //获取第k层(根节点层数为0)的节点个数的方法
    public int getKthLevelNodeCount(TreeNode root,int k){
        //空节点返回0
        if(root==null){
            return 0;
        }else if(k==0){
            //本层节点返回1
            return 1;
        }
        //递归左子树和右子树
        return getKthLevelNodeCount(root.left,k-1)+getKthLevelNodeCount(root.right, k);

    }

    //获取二叉树的深度的方法
    public int getHight(TreeNode root){
        //空节点返回-1
        if(root==null){
            return -1 ;
        }
        //递归左子树
        int leftHeight=getHight(root.left);
        //递归右子树
        int rightHeight=getHight(root.right);
        //返回其中最大值
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }



}
